//     链表

//1、 反转链表
//public class Solution {
//    public ListNode ReverseList(ListNode head) {
//        if(head == null){
//            return null;
//        }
//        ListNode prev =  head;
//        ListNode cur =  head.next;
//
//        while(cur != null){
//            ListNode curNext = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = curNext;
//        }
//        head.next = null;
//        return prev;
//    }
//}


// 2、链表内指定区间反转
//public class Solution {
//    public ListNode reverseBetween (ListNode head, int m, int n) {
//        ListNode newHead = new ListNode(-1);
//        newHead.next = head;
//        ListNode prev = newHead;
//        ListNode cur = head;
//        for(int i = 1;i < m;i++){
//            prev = cur;
//            cur = cur.next;
//        }
//        for(int i = m;i < n;i++){
//            ListNode curNext = cur.next;
//            cur.next = curNext.next;
//            curNext.next = prev.next;
//            prev.next = curNext;
//        }
//        return newHead.next;
//    }
//}


// 3、链表中的节点每k个一组翻转
//public class Solution {
//    public ListNode reverseKGroup (ListNode head, int k) {
//        // 找到每次翻转的尾部
//        ListNode tail = head;
//        // 遍历 k次到达尾部
//        for(int i = 0;i < k;i++){
//            if(tail == null){
//                return head;
//            }
//            tail = tail.next;
//        }
//        // 翻转时需要的前序和当前节点
//        ListNode prev = null;
//        ListNode cur = head;
//        while(cur != tail){
//            ListNode curNext = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = curNext;
//        }
//        // 当前尾指向下一段要反转的链表
//        head.next = reverseKGroup(tail,k);
//        return prev;
//    }
//}


// 4、合并两个排序的链表
//public class Solution {
//    public ListNode Merge(ListNode list1,ListNode list2) {
//        ListNode newHead = new ListNode(-1);
//        ListNode cur = newHead;
//        while(list1 != null && list2 != null){
//           if(list1.val > list2.val){
//               cur.next = list2;
//               list2 = list2.next;
//               cur = cur.next;
//           }else{
//               cur.next = list1;
//               list1 = list1.next;
//               cur = cur.next;
//           }
//        }
//        while(list1!= null){
//            cur.next = list1;
//            list1 = list1.next;
//            cur = cur.next;
//        }
//        while(list2 != null){
//            cur.next = list2;
//            list2 = list2.next;
//            cur = cur.next;
//        }
//        cur.next = null;
//        return newHead.next;
//    }
//}

// 5、合并K个已排序的列表
//public class Solution {
//    public ListNode mergeKLists(ArrayList<ListNode> lists) {
//        // k 个链表归并排序
//        return divideMerge(lists,0,lists.size()-1);
//    }
//    //划分合并区间函数
//    public ListNode divideMerge(ArrayList<ListNode> lists,int left,int right){
//        if(left > right){
//            return null;
//        }else if(left == right){
//            return lists.get(left);
//        }
//        int mid = (left + right)/2;
//        return merge(divideMerge(lists,left,mid),divideMerge(lists,mid+1,right));
//    }
//    //两个链表合并函数
//    public ListNode merge(ListNode list1,ListNode list2){
//        // 一个已经为空了，直接返回另一个
//        if(list1 == null || list2 == null){
//            return list1 == null ? list2 : list1;
//        }
//        // 添加一个表头
//        ListNode head = new ListNode(-1);
//        ListNode cur = head;
//         //两个链表都要不为空
//        while(list1 != null && list2 != null){
//            //取较小值的节点
//            if(list1.val <= list2.val){
//                cur.next = list1;
//                //只移动取值的指针
//                list1 = list1.next;
//            }else{
//                cur.next = list2;
//                //只移动取值的指针
//                list2 = list2.next;
//            }
//            //指针后移
//            cur = cur.next;
//        }
//         //哪个链表还有剩，直接连在后面
//        if(list1 != null){
//            cur.next = list1;
//        }else{
//            cur.next = list2;
//        }
//        //返回值去掉表头
//        return head.next;
//    }
//}


// 6、判断链表中是否有环
//public class Solution {
//    public boolean hasCycle(ListNode head) {
//        if(head == null){
//            return false;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        while(fast != null && fast.next != null){
//            fast = fast.next.next;
//            if(fast == slow){
//                return true;
//            }
//            slow = slow.next;
//        }
//        return false;
//    }
//}

// 7、链表中环的入口结点
//public class Solution {
//
//    public ListNode EntryNodeOfLoop(ListNode pHead) {
//        if(pHead == null){
//            return null;
//        }
//        ListNode fast = pHead;
//        ListNode slow = pHead;
//        boolean flag = false;
//        while(fast != null && fast.next != null){
//            fast = fast.next.next;
//            slow = slow.next;
//            if(fast == slow){
//                flag = true;
//                break;
//            }
//        }
//        if(!flag){
//            return null;
//        }
//        ListNode cur = pHead;
//        while(cur != slow){
//            slow = slow.next;
//            cur = cur.next;
//        }
//        return cur;
//    }
//}

// 8、链表中倒数最后k个结点
//public class Solution {
//    public ListNode FindKthToTail (ListNode pHead, int k) {
//        ListNode cur = pHead;
//        int count = 0;
//        while(cur!=null){
//            count++;
//            cur = cur.next;
//        }
//        if(count == 0){
//            return null;
//        }
//        if(count < k){
//            return null;
//        }
//        int temp = count - k;
//        while(temp-- > 0){
//            pHead = pHead.next;
//        }
//        return pHead;
//    }
//}

// 9、删除链表的倒数第n个节点
//public class Solution {
//    public ListNode removeNthFromEnd (ListNode head, int n) {
//        if(head == null){
//            return null;
//        }
//        ListNode tmp = head;
//        int count = 0;
//        while(tmp != null){
//            tmp = tmp.next;
//            count++;
//        }
//        if(n > count){
//            return head;
//        }else if(n == count){
//            return head.next;
//        }
//        int nums = count - n;
//        ListNode prev = null;
//        ListNode cur =  head;
//        while(0 < nums--){
//            prev = cur;
//            cur = cur.next;
//        }
//        prev.next = cur.next;
//        return head;
//    }
//}

// 10、两个链表的第一个公共结点
// 循环链表思维
//public class Solution {
//    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//        ListNode cur1 = pHead1, cur2 = pHead2;
//        while(cur1 != cur2){
//            cur1 = cur1 != null ? cur1.next : pHead2;
//            cur2 = cur2 != null ? cur2.next : pHead1;
//        }
//        return cur1;
//    }
//}

// 快慢指针
//public class Solution {
//    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//        int n1 = 0;
//        int n2 = 0;
//        ListNode head1 = pHead1;
//        while(head1 != null){
//            n1++;
//            head1 = head1.next;
//        }
//        ListNode head2 = pHead2;
//        while(head2 != null){
//            n2++;
//            head2 = head2.next;
//        }
//        if(n1 == 0 || n2 == 0){
//            return null;
//        }
//        ListNode cur1 = pHead1;
//        ListNode cur2 = pHead2;
//        int tmp = n1 - n2;
//        if(tmp > 0){
//            while(tmp-- > 0){
//                cur1 = cur1.next;
//            }
//        }else if(tmp < 0){
//            tmp = -tmp;
//            while(tmp-- > 0){
//                cur2 = cur2.next;
//            }
//        }
//        while(cur1 != cur2){
//            cur1 = cur1.next;
//            cur2 = cur2.next;
//        }
//        if(cur1 == null || cur2 == null){
//            return null;
//        }
//        return cur1;
//    }
//}


// 11、链表相加（二）
// 链表翻转思想
//public class Solution {
//    public ListNode reverseList(ListNode head) {
//        if (head == null) {
//            return head;
//        }
//        ListNode cur = head;
//        ListNode prev = null;
//        while (cur != null) {
//            ListNode curNext = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = curNext;
//        }
//        return prev;
//    }
//
//    public ListNode addInList(ListNode head1, ListNode head2) {
//        if (head1 == null || head2 == null) {
//            return head1 == null ? head2 : head1;
//        }
//        head1 = reverseList(head1);
//        head2 = reverseList(head2);
//        ListNode res = new ListNode(-1);
//        ListNode head = res;
//        int carry = 0;
//        while (head1 != null || head2 != null || carry != 0) {
//            int val1 = head1 == null ? 0 : head1.val;
//            int val2 = head2 == null ? 0 : head2.val;
//            int sum = val1 + val2 + carry;
//            carry = sum / 10;
//            head.next = new ListNode(sum % 10);
//            head = head.next;
//            if (head1 != null) {
//                head1 = head1.next;
//            }
//            if (head2 != null) {
//                head2 = head2.next;
//            }
//        }
//        return reverseList(res.next);
//    }
//}

// 栈
//public class Solution {
//    /**
//     *
//     * @param head1 ListNode类
//     * @param head2 ListNode类
//     * @return ListNode类
//     */
//    public ListNode addInList (ListNode head1, ListNode head2) {
//        ListNode tmp1 = head1;
//        Stack<ListNode> stack1 = new Stack<>();
//        while(tmp1 != null){
//            stack1.push(tmp1);
//            tmp1 = tmp1.next;
//        }
//        ListNode tmp2 = head2;
//        Stack<ListNode> stack2 = new Stack<>();
//        while(tmp2 != null){
//            stack2.push(tmp2);
//            tmp2 = tmp2.next;
//        }
//        if(stack1.isEmpty() ||  stack2.isEmpty()){
//            return stack1.isEmpty() ? head2 : head1;
//        }
//        ListNode newHead = new ListNode(-1);
//        int carry = 0;
//        while(!stack1.isEmpty() && !stack2.isEmpty()){
//            ListNode cur1 = stack1.pop();
//            ListNode cur2 = stack2.pop();
//            int num = cur1.val + cur2.val;
//            num += carry;
//            carry = num /10;
//            ListNode node = new ListNode(num%10);
//            if(newHead.next == null){
//                newHead.next = node;
//            }else{
//                node.next = newHead.next;
//                newHead.next = node;
//            }
//        }
//        while(!stack1.isEmpty()){
//            int num = stack1.pop().val + carry;
//            carry = num/ 10;
//            ListNode node = new ListNode(num%10);
//            node.next = newHead.next;
//            newHead.next = node;
//        }
//        while(!stack2.isEmpty()){
//            int num = stack2.pop().val + carry;
//            carry = num/10;
//            ListNode node = new ListNode(num%10);
//            node.next = newHead.next;
//            newHead.next = node;
//        }
//        if(carry > 0){
//            ListNode node = new ListNode(carry);
//            node.next = newHead.next;
//            newHead.next = node;
//        }
//        return newHead.next;
//    }
//}

// 12、单链表的排序
//public class Solution {
//    public ListNode sortInList (ListNode head) {
//        if(head == null || head.next == null){
//            return head;
//        }
//        ListNode left = head;
//        ListNode mid = head.next;
//        ListNode right = head.next.next;
//        while(right != null && right.next!= null){
//            left = left.next;
//            mid = mid.next;
//            right = right.next.next;
//        }
//        left.next = null;
//        return merge(sortInList(head),sortInList(mid));
//    }
//
//     ListNode merge(ListNode head1,ListNode head2){
//        if(head1 == null){
//            return head2;
//        }
//        if(head2 == null){
//            return head1;
//        }
//        ListNode head = new ListNode(0);
//        ListNode cur = head;
//        while(head1 != null && head2 != null){
//            if(head1.val <= head2.val){
//                cur.next = head1;
//                head1 = head1.next;
//            }else{
//                cur.next = head2;
//                head2 = head2.next;
//            }
//            cur = cur.next;
//        }
//        if(head1 != null){
//            cur.next = head1;
//        }else{
//            cur.next = head2;
//        }
//        return head.next;
//    }
//}

//13、 判断一个链表是否为回文结构
//public class Solution {
//    public boolean isPail (ListNode head) {
//        if(head == null){
//            return false;
//        }
//        if(head.next == null){
//            return true;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        ListNode prev = null;
//        while(fast != null && fast.next != null){
//            prev = slow;
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//        while(slow != null){
//            ListNode slowNext = slow.next;
//            slow.next = prev;
//            prev = slow;
//            slow = slowNext;
//        }
//        ListNode cur = head;
//        while(prev != cur){
//            if(prev.val !=  cur.val){
//                return false;
//            }
//            if(cur.next == prev){
//                return true;
//            }
//            prev = prev.next;
//            cur = cur.next;
//        }
//        return true;
//    }
//}

// 14、链表的奇偶重排
//public class Solution {
//    public ListNode oddEvenList (ListNode head) {
//        ListNode odd = new ListNode(0);
//        ListNode even = new ListNode(0);
//        ListNode oddCur = odd;
//        ListNode evenCur = even;
//        int count = 1;
//        ListNode cur = head;
//        while(cur!=null){
//            if(count % 2 == 0){
//                evenCur.next = cur;
//                evenCur = evenCur.next;
//            }else{
//                oddCur.next = cur;
//                oddCur = oddCur.next;
//            }
//            cur = cur.next;
//            count++;
//        }
//        oddCur.next = even.next;
//        evenCur.next = null;
//        return odd.next;
//    }
//}

// 15、 删除有序链表中重复的元素-I
//public class Solution {
//    public ListNode deleteDuplicates (ListNode head) {
//        if(head == null){
//            return head;
//        }
//        ListNode cur = head;
//        while(cur != null && cur.next != null){
//            if(cur.val == cur.next.val){
//                cur.next = cur.next.next;
//            }else{
//                cur = cur.next;
//            }
//        }
//        return head;
//    }
//}


// 16、 删除有序链表中重复的元素-II
//public class Solution {
//    public ListNode deleteDuplicates (ListNode head) {
//        if(head == null){
//            return head;
//        }
//        ListNode res =  new ListNode(0);
//        res.next = head;
//        ListNode cur = res;
//        while(cur.next != null && cur.next.next != null){
//            if(cur.next.val == cur.next.next.val){
//                int tmp = cur.next.val;
//                while(cur.next!= null && cur.next.val == tmp){
//                    cur.next = cur.next.next;
//                }
//            }else{
//                cur = cur.next;
//            }
//        }
//        return res.next;
//    }
//}


//   二分查找/排序

// 17、二分查找-I
//public class Solution {
//    public int search (int[] nums, int target) {
//        int i = 0;
//        int r = nums.length - 1;
//        while(i <= r){
//            int m = (i + r)/2;
//            if(nums[m] == target){
//                return m;
//            }
//            if(nums[m] > target){
//                r = m-1;
//            }else{
//                i = m + 1;
//            }
//        }
//        return -1;
//    }
//}

// 二维数组中的查找
//public class Solution {
//    public boolean Find(int target, int [][] array) {
//        if(array.length == 0){
//            return false;
//        }
//        int n = array.length;
//        if(array[0].length == 0){
//            return false;
//        }
//        int m = array[0].length;
//        for(int i = n -1,j=0;i >= 0 && j < m;){
//            if(array[i][j] > target){
//                i--;
//            }else if(array[i][j] < target){
//                j++;
//            }else{
//                return true;
//            }
//        }
//        return false;
//    }
//}

// 19、 寻找峰值
//public class Solution {
//    public int findPeakElement (int[] nums) {
//        int left = 0;
//        int right = nums.length - 1;
//        while(left < right){
//            int mid = (left + right)/2;
//            if(nums[mid] > nums[mid + 1]){
//                right = mid;
//            }else{
//                left = mid + 1;
//            }
//        }
//        return right;
//    }
//}


// 20、数组中的逆序对
//public class Solution {
//    public int mod = 1000000007;
//    public int InversePairs(int [] array) {
//        int n = array.length;
//        int[] res = new int[n];
//        return mergeSort(0,n-1,array,res);
//    }
//    public int mergeSort(int left,int right,int[] data,int[] temp){
//        if(left >= right){
//            return 0;
//        }
//        int mid = (left + right)/2;
//        int res = mergeSort(left,mid,data,temp) + mergeSort(mid + 1,right,data,temp);
//        res %= mod;
//        int i = left,j=mid+1;
//        for(int k = left;k <= right;k++){
//            temp[k] = data[k];
//        }
//        for(int k = left;k <= right;k++){
//            if(i == mid + 1){
//                data[k] = temp[j++];
//            }else if(j == right + 1 || temp[i] <= temp[j]){
//                data[k] = temp[i++];
//            }else{
//                data[k] = temp[j++];
//                res += mid - i + 1;
//            }
//        }
//        return res % mod;
//    }
//}

// 21、旋转数组的最小数字
//public class Solution {
//    public int minNumberInRotateArray(int [] array) {
//        int left = 0;
//        int right = array.length-1;
//        while(left < right){
//            int mid = (left + right)/2;
//            if(array[mid] > array[right]){
//                left = mid + 1;
//            }else if(array[mid] == array[right]){
//                right--;
//            }else{
//                right = mid;
//            }
//        }
//        return array[left];
//    }
//}

//比较版本号
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     * 比较版本号
//     * @param version1 string字符串
//     * @param version2 string字符串
//     * @return int整型
//     */
//    public int compare (String version1, String version2) {
//        int n1 = version1.length();
//        int n2 = version2.length();
//        int i = 0,j = 0;
//        while(i < n1 || j < n2){
//            long num1 = 0;
//            while(i < n1 && version1.charAt(i) != '.'){
//                num1 = num1 * 10 + (version1.charAt(i) - '0');
//                i++;
//            }
//            i++;
//            long num2 = 0;
//            while(j < n2 && version2.charAt(j) != '.'){
//                num2 = num2 * 10 + version2.charAt(j) - '0';
//                j++;
//            }
//            j++;
//            if(num1 > num2){
//                return 1;
//            }
//            if(num1 < num2){
//                return -1;
//            }
//        }
//        return 0;
//    }
//}


//        二叉树

// 23、二叉树的前序遍历
//public class Solution {
//    public int[] preorderTraversal (TreeNode root) {
//        List<Integer> list = new ArrayList<Integer>();
//        preorder(list,root);
//        int[] res = new int[list.size()];
//        for(int i = 0;i < list.size();i++){
//            res[i] = list.get(i);
//        }
//        return res;
//    }
//    public void preorder(List<Integer> list,TreeNode root){
//        if(root == null){
//            return;
//        }
//        list.add(root.val);
//        preorder(list,root.left);
//        preorder(list,root.right);
//    }
//
//}

// 24、 二叉树的中序遍历
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param root TreeNode类
//     * @return int整型一维数组
//     */
//    public int[] inorderTraversal (TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        inorder(list,root);
//        int[] res = new int[list.size()];
//        for(int i = 0;i < list.size();i++){
//            res[i] = list.get(i);
//        }
//        return res;
//    }
//    public void inorder(List<Integer> list,TreeNode root){
//        if(root == null){
//            return;
//        }
//        inorder(list,root.left);
//        list.add(root.val);
//        inorder(list,root.right);
//    }
//}

// 25、  二叉树后序遍历
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param root TreeNode类
//     * @return int整型一维数组
//     */
//    public int[]  postorderTraversal (TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        postorder(list,root);
//        int[] res = new int[list.size()];
//        for(int i = 0;i < list.size();i++){
//            res[i] = list.get(i);
//        }
//        return res;
//    }
//    public void  postorder(List<Integer> list,TreeNode root){
//        if(root == null){
//            return;
//        }
//        postorder(list,root.left);
//        postorder(list,root.right);
//        list.add(root.val);
//    }
//}

// 26、求二叉树的层序遍历
//public class Solution {
//    /**
//     *
//     * @param root TreeNode类
//     * @return int整型ArrayList<ArrayList<>>
//     */
//    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
//        if(root == null){
//            return new ArrayList();
//        }
//        Queue<TreeNode> queue = new LinkedList<>();
//        int size = 0;
//        ArrayList<ArrayList<Integer>> list =  new ArrayList<ArrayList<Integer>>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            size = queue.size();
//            ArrayList<Integer> arrayList = new ArrayList<>();
//            while(size-- > 0){
//                TreeNode cur = queue.poll();
//                arrayList.add(cur.val);
//                if(cur.left != null){
//                    queue.offer(cur.left);
//                }
//                if(cur.right != null){
//                    queue.offer(cur.right);
//                }
//            }
//            list.add(arrayList);
//        }
//        return list;
//    }
//}

// 27、按之字形顺序打印二叉树
//public class Solution {
//    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
//  if(root == null){
//           return new ArrayList();
//       }
//       Queue<TreeNode> queue = new LinkedList<>();
//       int size = 0;
//       ArrayList<ArrayList<Integer>> list =  new ArrayList<ArrayList<Integer>>();
//       queue.offer(root);
//       boolean  flag =  true;
//       while(!queue.isEmpty()){
//           size = queue.size();
//           ArrayList<Integer> arrayList = new ArrayList<>();
//           flag = !flag;
//           while(size-- > 0){
//               TreeNode cur = queue.poll();
//               arrayList.add(cur.val);
//               if(cur.left != null){
//                   queue.offer(cur.left);
//               }
//               if(cur.right != null){
//                   queue.offer(cur.right);
//               }
//           }
//           if(flag){
//               Collections.reverse(arrayList);
//           }
//            list.add(arrayList);
//       }
//       return list;
//    }
//
//}


//28 、二叉树的最大深度
//public class Solution {
//    /**
//     *
//     * @param root TreeNode类
//     * @return int整型
//     */
//    public int maxDepth (TreeNode root) {
//        if(root == null){
//            return 0;
//        }
//        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
//    }
//}

// 29、二叉树中和为某一值的路径(一)
//public class Solution {
//    /**
//     *
//     * @param root TreeNode类
//     * @param sum int整型
//     * @return bool布尔型
//     */
//    static int  res = 0;
//    public boolean hasPathSum (TreeNode root, int sum) {
//        if(root == null){
//            return false;
//        }
//        if(root.left == null && root.right == null && sum - root.val == 0){
//            return true;
//        }
//        return hasPathSum(root.left,sum -  root.val) || hasPathSum(root.right,sum - root.val);
//    }
//}

// 30、二叉搜索树与双向链表
//public class Solution {
//    public TreeNode Convert(TreeNode pRootOfTree) {
//        if(pRootOfTree == null){
//            return null;
//        }
//        inorderTraversal(pRootOfTree);
//        TreeNode head = pRootOfTree;
//        while(head.left != null){
//            head = head.left;
//        }
//        return head;
//    }
//    public TreeNode prev ;
//    public void inorderTraversal(TreeNode root){
//        if(root == null){
//            return;
//        }
//        inorderTraversal(root.left);
//        // 打印
//        root.left = prev;
//        if(prev != null){
//            prev.right = root;
//        }
//        prev = root;
////         System.out.print(root.val + " ");
//        inorderTraversal(root.right);
//    }
//}

// 31、对称的二叉树
//public class Solution {
//    boolean isSymmetrical(TreeNode pRoot) {
//        return recursion(pRoot,pRoot);
//    }
//    boolean recursion(TreeNode root1,TreeNode root2){
//        if(root1 == null && root2 == null){
//            return true;
//        }
//        if(root1 == null || root2 == null || root1.val != root2.val){
//            return false;
//        }
//        return recursion(root1.left,root2.right) && recursion(root1.right,root2.left);
//    }
//}

//32、合并二叉树
//public class Solution {
//    /**
//     *
//     * @param t1 TreeNode类
//     * @param t2 TreeNode类
//     * @return TreeNode类
//     */
//    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
//        if(t1 == null){
//            return t2;
//        }
//        if(t2 == null){
//            return t1;
//        }
//        TreeNode head = new TreeNode(t1.val + t2.val);
//        head.left = mergeTrees(t1.left,t2.left);
//        head.right = mergeTrees(t1.right,t2.right);
//        return head;
//    }
//}

// 33、二叉树的镜像
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param pRoot TreeNode类
//     * @return TreeNode类
//     */
//    public TreeNode Mirror (TreeNode root) {
//        if(root == null){
//            return null;
//        }
//        TreeNode left =  Mirror(root.left);
//        TreeNode right = Mirror(root.right);
//        root.right = left;
//        root.left =right;
//        return root;
//    }
//}

// 34、判断是不是二叉搜索树
//public class Solution {
//     int pre = Integer.MIN_VALUE;
//    public boolean isValidBST (TreeNode root) {
//        if(root== null){
//            return true;
//        }
//        if(!isValidBST(root.left)){
//            return false;
//        }
//        if(root.val < pre){
//            return false;
//        }
//        pre = root.val;
//        return isValidBST(root.right);
//    }
//}

// 35 判断是不是完全二叉树
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param root TreeNode类
//     * @return bool布尔型
//     */
//    public boolean isCompleteTree (TreeNode root) {
//        if(root == null){
//            return true;
//        }
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        TreeNode cur;
//        boolean notComplete = false;
//        while(!queue.isEmpty()){
//            cur = queue.poll();
//            if(cur == null){
//                notComplete = true;
//                continue;
//            }
//            if(notComplete){
//                return false;
//            }
//            queue.offer(cur.left);
//            queue.offer(cur.right);
//        }
//        return true;
//    }
//}

// 36 判断是不是平衡二叉树
//public class Solution {
//    public boolean IsBalanced_Solution(TreeNode root) {
//        if(root == null){
//            return true;
//        }
//        int left = deep(root.left);
//        int right =deep(root.right);
//        return Math.abs(left - right) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
//
//    }
//    public int deep(TreeNode root){
//        if(root == null){
//            return 0;
//        }
//        return Math.max(deep(root.left),deep(root.right)) + 1;
//    }
//}

// 37 二叉搜索树的最近公共祖先
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param root TreeNode类
//     * @param p int整型
//     * @param q int整型
//     * @return int整型
//     */
//    public int lowestCommonAncestor (TreeNode root, int p, int q) {
//        ArrayList<Integer> path_p = getPath(root,p);
//        ArrayList<Integer> path_q = getPath(root,q);
//        int res = 0;
//        for(int i = 0;i < path_p.size() && i < path_q.size();i++){
//            int x = path_p.get(i);
//            int y = path_q.get(i);
//            if(x == y){
//                res = x;
//            }else{
//                break;
//            }
//        }
//        return res;
//    }
//    public ArrayList<Integer> getPath(TreeNode root,int target){
//        ArrayList<Integer> path = new ArrayList<Integer>();
//        TreeNode node = root;
//        while(node.val != target){
//            path.add(node.val);
//            if(target < node.val){
//                node = node.left;
//            }else{
//                node = node.right;
//            }
//        }
//        path.add(node.val);
//        return path;
//    }
//}

// 38 在二叉树中找到两个节点的最近公共祖先
//public class Solution {
//
//    public boolean flag = false;
//    public void dfs(TreeNode root,ArrayList<Integer> path,int o){
//        if(flag || root == null){
//            return;
//        }
//        path.add(root.val);
//        if(root.val == o){
//            flag = true;
//            return;
//        }
//        dfs(root.left,path,o);
//        dfs(root.right,path,o);
//        if(flag){
//            return;
//        }
//        path.remove(path.size()-1);
//    }
//    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
//         ArrayList<Integer> path1 = new ArrayList<Integer>();
//         ArrayList<Integer> path2 = new ArrayList<Integer>();
//         dfs(root,path1,o1);
//         flag = false;
//         dfs(root,path2,o2);
//         int result = 0;
//         for(int i = 0;i < path1.size() && i < path2.size();i++){
//             int x = path1.get(i);
//             int y = path2.get(i);
//             if(x == y){
//                result = x;
//             }else{
//                 break;
//             }
//         }
//         return result;
//    }
//}

//39 序列化二叉树
//public class Solution {
//    private void SerializeFunction(TreeNode root,StringBuilder str){
//        if(root == null){
//            str.append("#");
//            return;
//        }
//        str.append(root.val).append('!');
//        SerializeFunction(root.left,str);
//        SerializeFunction(root.right,str);
//    }
//
//    String Serialize(TreeNode root) {
//        if(root == null){
//            return "#";
//        }
//        StringBuilder res = new StringBuilder();
//        SerializeFunction(root,res);
//        return res.toString();
//    }
//
//    TreeNode Deserialize(String str) {
//       if(str.equals("#")){
//           return null;
//       }
//       TreeNode res = DeserializeFunction(str);
//       return res;
//    }
//
//    public int index = 0;
//    private TreeNode  DeserializeFunction(String str){
//        if(str.charAt(index) == '#'){
//            index++;
//            return null;
//        }
//        int val = 0;
//        while(str.charAt(index) != '!' && index != str.length()){
//            val = val * 10 + (str.charAt(index) - '0');
//            index++;
//        }
//        TreeNode root = new TreeNode(val);
//        if(index == str.length()){
//            return root;
//        }else{
//            index++;
//        }
//        root.left = DeserializeFunction(str);
//        root.right = DeserializeFunction(str);
//        return root;
//    }
//}

// 40 重建二叉树
//public class Solution {
//    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
//        int n = pre.length;
//        int m = vin.length;
//        if(n == 0 || m == 0){
//            return null;
//        }
//        TreeNode root = new TreeNode(pre[0]);
//        for(int i = 0;i < vin.length;i++){
//            if(pre[0] == vin[i]){
//                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin, 0, i));
//                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i + 1, vin.length));
//                break;
//            }
//        }
//        return root;
//    }
//}

// 输出二叉树的右视图
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     * 求二叉树的右视图
//     * @param xianxu int整型一维数组 先序遍历
//     * @param zhongxu int整型一维数组 中序遍历
//     * @return int整型一维数组
//     */
//    public int[] solve (int[] xianxu, int[] zhongxu) {
//        if(xianxu.length == 0){
//            return new int[0];
//        }
//        TreeNode root = buildTree(xianxu,0,xianxu.length-1,zhongxu,0,zhongxu.length - 1);
//        ArrayList<Integer> temp = rightSideView(root);
//        int[] res = new int[temp.size()];
//        for(int i = 0;i < temp.size();i++){
//            res[i] = temp.get(i);
//        }
//        return res;
//    }
//
//    public TreeNode buildTree(int[] xianxu,int l1,int r1,int[] zhongxu,int l2,int r2){
//        if(l1 > r1 || l2 > r2){
//            return null;
//        }
//        TreeNode root = new TreeNode(xianxu[l1]);
//        int rootIndex = 0;
//        for(int i = l2;i <= r2;i++){
//            if(zhongxu[i] == xianxu[l1]){
//                rootIndex = i;
//                break;
//            }
//        }
//        int leftSize = rootIndex -l2;
//        int rightSize = r2 - rootIndex;
//        root.left = buildTree(xianxu,l1+1,l1 + leftSize,zhongxu,l2,l2+leftSize-1);
//        root.right = buildTree(xianxu,r1 - rightSize +1,r1,zhongxu,rootIndex + 1,r2);
//        return root;
//    }
//
//    public ArrayList<Integer> rightSideView(TreeNode root){
//        Map<Integer,Integer> map = new HashMap<>();
//        int max_depth = -1;
//        Stack<TreeNode> nodes = new Stack<>();
//        Stack<Integer> depths = new Stack<>();
//        nodes.push(root);
//        depths.push(0);
//        while(!nodes.isEmpty()){
//            TreeNode node = nodes.pop();
//            int depth = depths.pop();
//            if(node != null){
//                max_depth = Math.max(max_depth,depth);
//                if(map.get(depth)==null){
//                    map.put(depth,node.val);
//                }
//                nodes.push(node.left);
//                nodes.push(node.right);
//                depths.push(depth + 1);
//                depths.push(depth + 1);
//            }
//        }
//        ArrayList<Integer> res = new ArrayList<Integer>();
//        for(int i = 0;i <= max_depth;i++){
//            res.add(map.get(i));
//        }
//        return res;
//    }
//}

// 栈/堆/队列

// 42 用两个栈实现队列
//public class Solution {
//    Stack<Integer> stack1 = new Stack<Integer>();
//    Stack<Integer> stack2 = new Stack<Integer>();
//
//    public void push(int node) {
//        stack1.push(node);
//    }
//
//    public int pop() {
//        while(!stack1.isEmpty()){
//            stack2.push(stack1.pop());
//        }
//        int res = stack2.pop();
//        while(!stack2.isEmpty()){
//            stack1.push(stack2.pop());
//        }
//        return res;
//    }
//}

// 43 包含min函数的栈
//public class Solution {
//    Stack<Integer> s1 = new Stack<Integer>();
//    Stack<Integer> s2 = new Stack<Integer>();
//    public void push(int node) {
//        s1.push(node);
//        if(s2.isEmpty() || s2.peek() > node){
//            s2.push(node);
//        }else{
//            s2.push(s2.peek());
//        }
//    }
//
//    public void pop() {
//        s1.pop();
//        s2.pop();
//    }
//
//    public int top() {
//        return s1.peek();
//    }
//
//    public int min() {
//        return s2.peek();
//    }
//}

// 44 有效括号序列
//public class Solution {
//    /**
//     *
//     * @param s string字符串
//     * @return bool布尔型
//     */
//    public boolean isValid (String s) {
//        Stack<Character> st = new Stack<Character>();
//        for(int i = 0;i < s.length();i++){
//            if(s.charAt(i) == '('){
//                st.push(')');
//            }else if(s.charAt(i) == '['){
//                st.push(']');
//            }else if(s.charAt(i) == '{'){
//                st.push('}');
//            }else if(st.isEmpty() || st.pop() != s.charAt(i)){
//                return false;
//            }
//        }
//        return st.isEmpty();
//    }
//}

// 45 滑动窗口的最大值
// 遍历思想
//public class Solution {
//    public ArrayList<Integer> maxInWindows(int [] num, int size) {
//        int len = num.length;
//        ArrayList<Integer> list = new ArrayList<Integer>();
//        if( size == 0 || size > len){
//            return list;
//        }
//        int max = Integer.MIN_VALUE;
//        for(int i = 0; i < len;i++){
//            int tmp = 0;
//            for(int j = i;j < i + size && j < len;j++){
//                max = Math.max(max,num[j]);
//                tmp++;
//            }
//            if(tmp == size){
//                list.add(max);
//                max = Integer.MIN_VALUE;
//            }else{
//                break;
//            }
//        }
//        return list;
//    }
//}

// 队列解法
//import java.util.*;
//public class Solution {
//    public ArrayList<Integer> maxInWindows(int [] num, int size) {
//        ArrayList<Integer> res = new ArrayList<Integer>();
//        //窗口大于数组长度的时候，返回空
//        if(size <= num.length && size != 0){
//            //双向队列
//            ArrayDeque <Integer> dq = new ArrayDeque<Integer>();
//            //先遍历一个窗口
//            for(int i = 0; i < size; i++){
//                //去掉比自己先进队列的小于自己的值
//                while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
//                    dq.pollLast();
//                dq.add(i);
//            }
//            //遍历后续数组元素
//            for(int i = size; i < num.length; i++){
//                //取窗口内的最大值
//                res.add(num[dq.peekFirst()]);
//                while(!dq.isEmpty() && dq.peekFirst() < (i - size + 1))
//                    //弹出窗口移走后的值
//                    dq.pollFirst();
//                //加入新的值前，去掉比自己先进队列的小于自己的值
//                while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
//                    dq.pollLast();
//                dq.add(i);
//            }
//            res.add(num[dq.pollFirst()]);
//        }
//        return res;
//    }
//}

// 46 最小的K个数
//public class Solution {
//    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
//        ArrayList<Integer> list = new ArrayList<>();
//        if(input.length < k || k == 0){
//            return list;
//        }
//        PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));
//        for(int i = 0;i < k;i++){
//            q.offer(input[i]);
//        }
//        for(int i = k;i < input.length;i++){
//            if(q.peek() > input[i]){
//                q.poll();
//                q.offer(input[i]);
//            }
//        }
//        for(int i = 0;i < k;i++){
//            list.add(q.poll());
//        }
//        return list;
//    }
//}

// 47 寻找第K大
//public class Solution {
//    public int findKth(int[] a, int n, int K) {
//        PriorityQueue<Integer> p = new PriorityQueue<>();
//        if(K > n ){
//            return -1;
//        }
//        for(int i = 0;i < K;i++){
//            p.offer(a[i]);
//        }
//        for(int i = K;i < n;i++){
//            if(p.peek() < a[i]){
//                p.poll();
//                p.offer(a[i]);
//            }
//        }
//        return p.poll();
//    }
//}

// 48 数据流中的中位数
//public class Solution {
//    private ArrayList<Integer> val = new ArrayList<Integer>();
//    public void Insert(Integer num) {
//        if(val.isEmpty()){
//            val.add(num);
//        }else{
//            int i = 0;
//            for(;i < val.size();i++){
//                if(num <= val.get(i)){
//                    break;
//                }
//            }
//            val.add(i,num);
//        }
//    }
//
//    public Double GetMedian() {
//        int n =  val.size();
//        if(n % 2 == 1){
//            return (double)val.get(n/2);
//        }else{
//            double a = val.get(n/2);
//            double b = val.get(n/2 -1);
//            return (a + b)/2;
//        }
//    }
//}

// 49 表达式求值
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     * 返回表达式的值
//     * @param s string字符串 待计算的表达式
//     * @return int整型
//     */
//    public int solve (String s) {
//       ArrayList<Integer> res = function(s,0);
//       return res.get(0);
//    }
//
//    public ArrayList<Integer> function(String s,int index){
//        Stack<Integer> stack = new Stack<Integer>();
//        int num = 0;
//        char op = '+';
//        int i;
//        for(i = index;i < s.length();i++){
//            if(s.charAt(i)>='0' && s.charAt(i)<= '9'){
//                num = num * 10 + s.charAt(i) - '0';
//                if(i != s.length() - 1){
//                    continue;
//                }
//            }
//            if(s.charAt(i) == '('){
//                ArrayList<Integer> res = function(s,i+1);
//                num = res.get(0);
//                i = res.get(1);
//                if(i != s.length() - 1){
//                    continue;
//                }
//            }
//            switch(op){
//                case '+':
//                    stack.push(num);
//                    break;
//                case '-':
//                    stack.push(-num);
//                    break;
//                case '*':
//                    int temp = stack.pop();
//                    stack.push(temp * num);
//                    break;
//            }
//            num = 0;
//            if(s.charAt(i) == ')'){
//                break;
//            }else{
//                op =s.charAt(i);
//            }
//        }
//        int sum = 0;
//        while(!stack.isEmpty()){
//            sum += stack.pop();
//        }
//        ArrayList<Integer> temp = new ArrayList<>();
//        temp.add(sum);
//        temp.add(i);
//        return temp;
//    }
//}

//  哈希

// 50 两数之和
//public class Solution {
//    /**
//     *
//     * @param numbers int整型一维数组
//     * @param target int整型
//     * @return int整型一维数组
//     */
//    public int[] twoSum (int[] numbers, int target) {
//        HashMap<Integer,Integer> map = new HashMap<>();
//        for(int i = 0;i < numbers.length;i++){
//            int temp = target - numbers[i];
//            if(!map.containsKey(temp)){
//                map.put(numbers[i],i);
//            }else{
//                return new int[]{map.get(temp)+1,i+1};
//            }
//        }
//        return new int[0];
//    }
//}

// 51 数组中出现次数超过一半的数字
//public class Solution {
//    public int MoreThanHalfNum_Solution(int [] array) {
//        HashMap<Integer,Integer> map = new HashMap<>();
//        for(int i = 0;i < array.length;i++){
//            if(map.containsKey(array[i])){
//                map.put(array[i],map.get(array[i])+1);
//            }else{
//                map.put(array[i],1);
//            }
//        }
//        for(int i = 0;i < array.length;i++){
//            if(map.get(array[i]) > array.length/2){
//                return array[i];
//            }
//        }
//        return -1;
//    }
//}

// 52 数组中只出现一次的两个数字

// Set集合
//public class Solution {
//    public int[] FindNumsAppearOnce (int[] array) {
//        Set<Integer> set = new TreeSet<>();
//        for(int i = 0;i < array.length;i++){
//            if(!set.add(array[i])){
//                set.remove(array[i]);
//            }
//        }
//        Object[] arr = set.toArray();
//        int[] res = new int[arr.length];
//        for(int i =0;i < arr.length;i++){
//            res[i] = Integer.valueOf(arr[i].toString());
//        }
//        return res;
//    }

// map集合
//public class Solution {
//    public int[] FindNumsAppearOnce (int[] array) {
//        Map<Integer,Integer> map = new HashMap<>();
//        ArrayList<Integer> list = new ArrayList<>();
//        for(int i = 0;i < array.length;i++){
//            if(!map.containsKey(array[i])){
//                map.put(array[i],1);
//            }else{
//                map.put(array[i],map.get(array[i])+ 1);
//            }
//        }
//        for(int i = 0;i < array.length;i++){
//            if(map.get(array[i]) == 1){
//                list.add(array[i]);
//            }
//        }
//        if(list.get(0) > list.get(1)){
//            return new int[]{list.get(1),list.get(0)};
//        }
//        return new int[]{list.get(0),list.get(1)};
//    }
//}

// 53 缺失的第一个正整数
//public class Solution {
//    public int minNumberDisappeared (int[] nums) {
//        int n = nums.length;
//        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
//        for(int i = 0;i < n;i++){
//            map.put(nums[i],i);
//        }
//        int res = 1;
//        while(map.containsKey(res)){
//            res++;
//        }
//        return res;
//    }
//}

//54 三数之和
//public class Solution {
//    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
//        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
//        int n = num.length;
//        if(n < 3){
//            return list;
//        }
//        Arrays.sort(num);
//        for(int i = 0;i < n -2;i++){
//            if(i != 0 && num[i] == num[i-1]){
//                continue;
//            }
//            int left = i + 1;
//            int right = n - 1;
//            int target = -num[i];
//            while(left < right){
//                if(num[left] + num[right] == target){
//                    ArrayList<Integer> temp = new ArrayList<>();
//                    temp.add(num[i]);
//                    temp.add(num[left]);
//                    temp.add(num[right]);
//                    list.add(temp);
//                    while(left + 1 < right && num[left] == num[left + 1]){
//                        left++;
//                    }
//                    while(right - 1 > left && num[right] == num[right - 1]){
//                        right--;
//                    }
//                    left++;
//                    right--;
//                }else if(num[left] + num[right] > target){
//                    right--;
//                }else{
//                    left++;
//                }
//            }
//        }
//        return list;
//    }
//}

//  递归/回溯

// 55 没有重复项数字的全排列
//public class Solution {
//    public ArrayList<ArrayList<Integer>> permute(int[] num) {
//        Arrays.sort(num);
//        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
//        ArrayList<Integer> nums = new ArrayList<Integer>();
//        for(int i =0;i < num.length;i++){
//            nums.add(num[i]);
//        }
//        recursion(res,nums,0);
//        return res;
//    }
//    public void recursion(ArrayList<ArrayList<Integer>> res,ArrayList<Integer> num,int index){
//        if(index == num.size() - 1){
//            res.add(num);
//        }else{
//            for(int i = index;i < num.size();i++){
//                swap(num,i,index);
//                recursion(res,num,index + 1);
//                swap(num,i,index);
//            }
//        }
//    }
//    private void swap(ArrayList<Integer> num,int i1,int i2){
//        int tmp = num.get(i1);
//        num.set(i1,num.get(i2));
//        num.set(i2,tmp);
//    }
//}

// 56 有重复项数字的全排列
//public class Solution {
//    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
//        Arrays.sort(num);
//        Boolean[] vis = new Boolean[num.length];
//        Arrays.fill(vis,false);
//        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
//        ArrayList<Integer> temp = new ArrayList<>();
//        recursion(res,num,temp,vis);
//        return  res;
//    }
//    public void recursion(ArrayList<ArrayList<Integer>> res,int[] num,ArrayList<Integer> temp,Boolean[] vis){
//        if(temp.size() ==  num.length){
//            res.add(new ArrayList<Integer>(temp));
//            return;
//        }
//        for(int i = 0;i < num.length;i++){
//            if(vis[i]){
//                continue;
//            }
//            if(i > 0 && num[i-1] == num[i] && !vis[i-1]){
//                continue;
//            }
//            vis[i] = true;
//            temp.add(num[i]);
//            recursion(res,num,temp,vis);
//            vis[i] = false;
//            temp.remove(temp.size()-1);
//        }
//    }
//}

// 57 岛屿数量
//public class Solution {
//    /**
//     * 判断岛屿数量
//     * @param grid char字符型二维数组
//     * @return int整型
//     */
//    public int solve (char[][] grid) {
//        int n = grid.length;
//        if(n == 0){
//            return 0;
//        }
//        int m = grid[0].length;
//        int count = 0;
//        for(int i = 0;i < n;i++){
//            for(int j = 0;j < m;j++){
//                if(grid[i][j] == '1'){
//                    count++;
//                    dfs(grid,i,j);
//                }
//            }
//        }
//        return count;
//    }
//    public void dfs(char[][] grid,int i,int j){
//        int n = grid.length;
//        int m = grid[0].length;
//        grid[i][j] = '0';
//        if(i - 1 >=  0 && grid[i-1][j] == '1'){
//            dfs(grid,i-1,j);
//        }
//        if(i + 1 < n && grid[i+1][j] == '1'){
//            dfs(grid,i+1,j);
//        }
//        if(j - 1 >= 0 && grid[i][j-1] == '1'){
//            dfs(grid,i,j-1);
//        }
//        if(j + 1 < m && grid[i][j+1] == '1'){
//            dfs(grid,i,j+1);
//        }
//    }
//}

// 58 字符串的排列
//public class Solution {
//    public ArrayList<String> Permutation(String str) {
//       ArrayList<String> res = new ArrayList<>();
//       if(str == null || str.length() == 0){
//           return res;
//       }
//       char[] charStr = str.toCharArray();
//       Arrays.sort(charStr);
//       boolean[] vis = new boolean[str.length()];
//       Arrays.fill(vis,false);
//       StringBuffer temp = new StringBuffer();
//       recursion(res,charStr,temp,vis);
//       return res;
//    }
//    public void recursion(ArrayList<String> res,char[] str,StringBuffer temp,boolean[] vis){
//        if(temp.length() == str.length){
//            res.add(new String(temp));
//            return;
//        }
//        for(int i = 0;i < str.length;i++){
//            if(vis[i]){
//                continue;
//            }
//            if(i > 0 && str[i] == str[i-1] && !vis[i-1]){
//                continue;
//            }
//            vis[i] = true;
//            temp.append(str[i]);
//            recursion(res,str,temp,vis);
//            vis[i]=false;
//            temp.deleteCharAt(temp.length()-1);
//        }
//
//    }
//}

// 59 N皇后问题
//public class Solution {
//    /**
//     *
//     * @param n int整型 the n
//     * @return int整型
//     */
//    private int res;
//    public int Nqueen (int n) {
//        res = 0;
//        int[] pos = new int[n];
//        Arrays.fill(pos,0);
//        recursion(n,0,pos);
//        return res;
//    }
//
//    public void recursion(int n,int row,int[] pos){
//        if(row == n){
//            res++;
//            return;
//        }
//        for(int i = 0;i < n;i++){
//            if(isValid(pos,row,i)){
//                pos[row] = i;
//                recursion(n,row+1,pos);
//            }
//        }
//    }
//
//    public boolean isValid(int[] pos,int row,int col){
//        for(int i = 0;i < row;i++){
//            if( col == pos[i] || Math.abs(row-i) == Math.abs(col - pos[i])){
//                return false;
//            }
//        }
//        return true;
//    }
//}

// 60 括号生成
//public class Solution {
//    /**
//     *
//     * @param n int整型
//     * @return string字符串ArrayList
//     */
//    public ArrayList<String> generateParenthesis (int n) {
//        ArrayList<String> res = new ArrayList<>();
//        recursion(0,0,"",res,n);
//        return res;
//    }
//
//    public void recursion(int left,int right,String temp,ArrayList<String> res,int n){
//        if(left == n && right == n){
//            res.add(temp);
//            return;
//        }
//        if(left < n){
//            recursion(left + 1,right,temp + "(" ,res,n);
//        }
//        if(right < n && left > right){
//            recursion(left,right+ 1,temp+")",res,n);
//        }
//    }
//}

// 61 矩阵最长递增路径
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     * 递增路径的最大长度
//     * @param matrix int整型二维数组 描述矩阵的每个数
//     * @return int整型
//     */
//    private int[][] dirs = new int[][] {{-1,0},{1,0},{0,1},{0,-1}};
//    private int n,m;
//    public int solve (int[][] matrix) {
//        if(matrix.length == 0 || matrix[0].length == 0){
//            return 0;
//        }
//        int res = 0;
//        n = matrix.length;
//        m = matrix[0].length;
//        int[][] dp = new int[m+1][n+1];
//        for(int i = 0;i < n;i++){
//            for(int j = 0;j < m;j++){
//                res = Math.max(res,dfs(matrix,dp,i,j));
//            }
//        }
//        return res;
//    }
//
//    public int dfs(int[][] matrix,int[][] dp,int i,int j){
//        if(dp[i][j] != 0){
//            return dp[i][j];
//        }
//        dp[i][j]++;
//        for(int k = 0;k < 4;k++){
//            int nexti = i + dirs[k][0];
//            int nextj = j + dirs[k][1];
//            if(nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] > matrix[i][j]){
//                dp[i][j] =  Math.max(dp[i][j],dfs(matrix,dp,nexti,nextj)+1);
//            }
//        }
//        return dp[i][j];
//    }
//}

// 动态规划

// 62 斐波那契数列
//public class Solution {
//    public int Fibonacci(int n) {
//        if(n < 3){
//            return 1;
//        }
//        int a = 1;
//        int b = 1;
//        int c = a + b;
//        while(n-- > 3){
//            a = b;
//            b = c;
//            c = a + b;
//        }
//        return c;
//    }
//}

// 63 跳台阶
//public class Solution {
//    public int jumpFloor(int target) {
//        if(target == 1){
//            return 1;
//        }
//        if(target == 2){
//            return 2;
//        }
//        int a = 1;
//        int b = 2;
//        int c = a + b;
//        while(target-- > 3){
//            a = b;
//            b = c;
//            c = a + b;
//        }
//        return c;
//    }
//}

// 64 最小花费爬楼梯
//public class Solution {
//    public int minCostClimbingStairs (int[] cost) {
//        int[] dp = new int[cost.length + 1];
//        for(int i = 2;i <= cost.length;i++){
//            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
//        }
//        return dp[cost.length];
//    }
//}

// 65 最长公共子序列(二)
//public class Solution {
//    /**
//     * longest common subsequence
//     * @param s1 string字符串 the string
//     * @param s2 string字符串 the string
//     * @return string字符串
//     */
//     private String x = "";
//     private String y = "";
//    public String LCS (String s1, String s2) {
//        int n1 = s1.length();
//        int n2 = s2.length();
//        if(n1 == 0 || n2 == 0){
//            return "-1";
//        }
//        x = s1;
//        y = s2;
//        int[][] dp = new int[n1+1][n2 + 1];
//        int[][] b = new int[n1+1][n2+1];
//        for(int i = 1;i <= n1;i++){
//            for(int j = 1;j <= n2;j++){
//                if(s1.charAt(i-1) == s2.charAt(j-1)){
//                    dp[i][j] = dp[i-1][j-1]+1;
//                    b[i][j] = 1;
//                }else{
//                    if(dp[i-1][j] > dp[i][j-1]){
//                        dp[i][j] = dp[i-1][j];
//                        b[i][j] = 2;
//                    }else{
//                        dp[i][j] = dp[i][j-1];
//                        b[i][j] = 3;
//                    }
//                }
//            }
//        }
//        String res = ans(n1,n2,b);
//        if(res.isEmpty()){
//            return "-1";
//        }
//        return res;
//    }
//
//    String ans(int i,int j,int[][] b){
//        String res ="";
//        if(i == 0 || j == 0){
//            return res;
//        }
//        if(b[i][j] == 1){
//            res += ans(i-1,j-1,b);
//            res += x.charAt(i-1);
//        }else if(b[i][j] == 2){
//            res += ans(i-1,j,b);
//        }else if(b[i][j] == 3){
//            res += ans(i,j-1,b);
//        }
//        return res;
//    }
//}

// 66 最长公共子串
//public class Solution {
//    public String LCS (String str1, String str2) {
//        int len = 0;
//        String res = "";
//        for(int i = 0;i < str1.length();i++){
//            for(int j = 0;j < str2.length();j++){
//                int temp = 0;
//                StringBuffer temps = new StringBuffer();
//                int x = i,y = j;
//                while(x < str1.length() && y < str2.length() && str1.charAt(x) == str2.charAt(y)){
//                    temps.append(str1.charAt(x));
//                    x++;
//                    y++;
//                    temp++;
//                }
//                if(len < temp){
//                    len = temp;
//                    res = temps.toString();
//                }
//            }
//        }
//        return res;
//    }
//}

// 67 不同路径的数目(一)
//public class Solution {
//    /**
//     *
//     * @param m int整型
//     * @param n int整型
//     * @return int整型
//     */
//    public int uniquePaths (int m, int n) {
//        if(m == 1 || n == 1){
//            return 1;
//        }
//        return uniquePaths(m - 1,n) + uniquePaths(m,n - 1);
//    }
//}

// 68 矩阵的最小路径和
//public class Solution {
//    public int minPathSum (int[][] matrix) {
//        int n = matrix.length;
//        int m = matrix[0].length;
//        int[][] dp = new int[n][m];
//        dp[0][0] = matrix[0][0];
//        for(int i = 1;i < n;i++){
//            dp[i][0] = matrix[i][0] + dp[i - 1][0];
//        }
//        for(int i = 1;i < m;i++){
//            dp[0][i] = matrix[0][i] + dp[0][i-1];
//        }
//        for(int i = 1;i < n;i++){
//            for(int j = 1;j < m;j++){
//                dp[i][j] = matrix[i][j] + (dp[i-1][j] > dp[i][j-1] ? dp[i][j-1] : dp[i-1][j]);
//            }
//        }
//        return dp[n-1][m-1];
//    }
//}

// 69 把数字翻译成字符串
//public class Solution {
//    /**
//     * 解码
//     * @param nums string字符串 数字串
//     * @return int整型
//     */
//    public int solve (String nums) {
//        if(nums.equals("0")){
//            return 0;
//        }
//        if(nums == "10" || nums == "20"){
//            return 1;
//        }
//        for(int i = 1;i < nums.length();i++){
//            if(nums.charAt(i) == '0'){
//                if(nums.charAt(i-1) != '1' && nums.charAt(i-1) != '2'){
//                    return 0;
//                }
//            }
//        }
//        int[] dp = new int[nums.length() + 1];
//        Arrays.fill(dp,1);
//        for(int i = 2;i <= nums.length();i++){
//            if(nums.charAt(i-2) == '1' && nums.charAt(i-1) != '0' || (nums.charAt(i-2) == '2')
//            && nums.charAt(i-1) > '0' && nums.charAt(i-1)<'7'){
//                dp[i] = dp[i-1] + dp[i-2];
//            }else{
//                dp[i] = dp[i-1];
//            }
//        }
//        return dp[nums.length()];
//    }
//}

// 70 兑换零钱(一)
//public class Solution {
//    /**
//     * 最少货币数
//     * @param arr int整型一维数组 the array
//     * @param aim int整型 the target
//     * @return int整型
//     */
//    public int minMoney (int[] arr, int aim) {
//        if(aim < 1){
//            return 0;
//        }
//        int[] dp = new int[aim+1];
//        Arrays.fill(dp,aim+1);
//        dp[0] = 0;
//        for(int i = 1;i <= aim;i++){
//            for(int j = 0;j < arr.length;j++){
//                if(arr[j] <= i){
//                    dp[i] = Math.min(dp[i],dp[i - arr[j]] + 1);
//                }
//            }
//        }
//        return dp[aim] > aim ? -1 : dp[aim];
//    }
//}

// 71 最长上升子序列(一)
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     * 给定数组的最长严格上升子序列的长度。
//     * @param arr int整型一维数组 给定的数组
//     * @return int整型
//     */
//    public int LIS (int[] arr) {
//        int[] dp = new int[arr.length];
//        Arrays.fill(dp,1);
//        int res = 0;
//        if(arr.length == 1){
//            return 1;
//        }
//        for(int i = 1;i < arr.length;i++){
//            for(int j = 0;j < i;j++){
//                if(arr[i] > arr[j] && dp[i] < dp[j] + 1){
//                    dp[i] = dp[j]+1;
//                    res = Math.max(res,dp[i]);
//                }
//            }
//        }
//        return res;
//    }
//}

// 72 连续子数组的最大和
//public class Solution {
//    public int FindGreatestSumOfSubArray(int[] array) {
//        int n = array.length;
//        int[] dp = new int[n];
//        dp[0] = array[0];
//        int maxSum = dp[0];
//        for(int i = 1;i < n;i++){
//            dp[i] = Math.max(dp[i-1]+array[i],array[i]);
//            maxSum = Math.max(maxSum,dp[i]);
//        }
//        return maxSum;
//    }
//}

// 73 最长回文子串
//public class Solution {
//    public int getLongestPalindrome (String A) {
//        int maxLen = 1;
//        for(int i = 0;i < A.length() - 1;i++){
//            maxLen = Math.max(maxLen,Math.max(fun(A,i,i),fun(A,i,i+1)));
//        }
//        return maxLen;
//    }
//
//    public int fun(String s,int begin,int end){
//        while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
//            begin--;
//            end++;
//        }
//        return end - begin - 1;
//    }
//}

// 74 数字字符串转化成IP地址
//public class Solution {
//    public ArrayList<String> restoreIpAddresses (String s) {
//        ArrayList<String> res = new ArrayList<>();
//        int n = s.length();
//        for(int i = 1;i < 4 && i < n -2;i++){
//            for(int j = i + 1;j < i + 4 && j < n - 1;j++){
//                for(int k = j + 1;k < j + 4 && k< n;k++){
//                    if(n - k >= 4){
//                        continue;
//                    }
//                    String a = s.substring(0,i);
//                    String b = s.substring(i,j);
//                    String c = s.substring(j,k);
//                    String d = s.substring(k);
//                    if(Integer.parseInt(a) > 255 || Integer.parseInt(b) > 255 || Integer.parseInt(c) > 255 || Integer.parseInt(d) > 255){
//                        continue;
//                    }
//                    if(a.length() != 1 && a.charAt(0) == '0' || b.length() != 1 && b.charAt(0) == '0' || c.length() != 1 && c.charAt(0) == '0' || d.length() != 1 && d.charAt(0) == '0' ){
//                        continue;
//                    }
//                    String temp = a + "." + b +"."+ c + "." + d;
//                    res.add(temp);
//                }
//            }
//        }
//        return res;
//    }
//}

// 75 编辑距离(一)
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param str1 string字符串
//     * @param str2 string字符串
//     * @return int整型
//     */
//    public int editDistance (String str1, String str2) {
//        int n1 = str1.length();
//        int n2 = str2.length();
//        int[][] dp = new int[n1+1][n2 + 1];
//        for(int i = 1;i <= n1;i++){
//            dp[i][0] = dp[i - 1][0] + 1;
//        }
//        for(int i = 1;i <= n2;i++){
//            dp[0][i] = dp[0][i - 1] + 1;
//        }
//        for(int i = 1;i <= n1;i++){
//            for(int j = 1;j <= n2;j++){
//                if(str1.charAt(i - 1) == str2.charAt(j - 1)){
//                    dp[i][j] = dp[i-1][j -1];
//                }else{
//                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
//                }
//            }
//        }
//        return dp[n1][n2];
//    }
//}

// 76 正则表达式匹配
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param str string字符串
//     * @param pattern string字符串
//     * @return bool布尔型
//     */
//    public boolean match (String str, String pattern) {
//        int n1 = str.length();
//        int n2 = pattern.length();
//        boolean[][] dp = new boolean[n1+1][n2+1];
//        for(int i = 0;i <= n1;i++){
//            for(int j = 0;j <= n2;j++){
//                if(j == 0){
//                    dp[i][j] = (i == 0 ? true : false);
//                }else{
//                    if(pattern.charAt(j-1) != '*'){
//                        if(i > 0 && (str.charAt(i-1) == pattern.charAt(j-1) || pattern.charAt(j-1) == '.')){
//                            dp[i][j] = dp[i-1][j-1];
//                        }
//                    }else{
//                        if(j >= 2){
//                            dp[i][j] |= dp[i][j-2];
//                        }
//                         if(i >= 1 && j >= 2 && (str.charAt(i-1) == pattern.charAt(j-2) || pattern.charAt(j-2)=='.')){
//                            dp[i][j] |= dp[i-1][j];
//                        }
//                    }
//                }
//            }
//        }
//        return dp[n1][n2];
//    }
//}

// 77 最长的括号子串
//public class Solution {
//    /**
//     *
//     * @param s string字符串
//     * @return int整型
//     */
//    public int longestValidParentheses (String s) {
//        int res =0;
//        int start = -1;
//        Stack<Integer> st = new Stack<Integer>();
//        for(int i = 0;i < s.length();i++){
//            if(s.charAt(i) == '('){
//                st.push(i);
//            }else{
//                if(st.isEmpty()){
//                    start = i;
//                }else{
//                    st.pop();
//                    if(!st.isEmpty()){
//                        res = Math.max(res,i-st.peek());
//                    }else{
//                        res = Math.max(res,i-start);
//                    }
//                }
//            }
//        }
//        return res;
//    }
//}

// 78 打家劫舍(一)
//public class Solution {
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param nums int整型一维数组
//     * @return int整型
//     */
//    public int rob (int[] nums) {
//        int[] dp = new int[nums.length+1];
//        dp[1] = nums[0];
//        for(int i = 2;i <= nums.length;i++){
//            dp[i] = Math.max(dp[i-1],nums[i-1] + dp[i-2]);
//        }
//        return dp[nums.length];
//    }
//}

// 79 打家劫舍(二)
//public class Solution {
//    public int rob (int[] nums) {
//        int[] dp = new int[nums.length+1];
//        dp[1] = nums[0];
//        for(int i = 2;i < nums.length;i++){
//            dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i-1]);
//        }
//        int res = dp[nums.length - 1];
//        Arrays.fill(dp,0);
//        for(int i = 2;i <= nums.length;i++){
//            dp[i] = Math.max(dp[i-1],nums[i-1] + dp[i-2]);
//        }
//        return Math.max(res,dp[nums.length]);
//    }
//}

// 80 买卖股票的最好时机(一)
//public class Solution {
//    public int maxProfit (int[] prices) {
//        int n = prices.length;
// dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
//        int[][] dp = new int[n][2];
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        for(int i = 1;i < n;i++){
//            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
//            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
//        }
//        return dp[n-1][0];
//    }
//}

// 81 买卖股票的最好时机(二)
//public class Solution {
//    public int maxProfit (int[] prices) {
//        int n = prices.length;
//        int[][] dp = new int[n][2];
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        for(int i = 1;i < n;i++){
//            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
//            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
//        }
//        return dp[n-1][0];
//    }
//}

// 82 买卖股票的最好时机(三)
//public class Solution {
//    public int maxProfit (int[] prices) {
//        int n = prices.length;
//        int[][] dp = new int[n][5];
//        Arrays.fill(dp[0],-10000);
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        for(int i = 1;i < n;i++){
//            dp[i][0] = dp[i-1][0];
//            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
//            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1] + prices[i]);
//            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2] - prices[i]);
//            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3] + prices[i]);
//        }
//        return Math.max(dp[n-1][2],Math.max(0,dp[n-1][4]));
//    }
//}

//   字符串

// 83 字符串变形
//public class Solution {
//    public String trans(String s, int n) {
//        if(n == 0){
//            return s;
//        }
//        StringBuffer res = new StringBuffer();
//        for(int i = 0;i < n;i++){
//            if(s.charAt(i) <= 'Z' && s.charAt(i) >= 'A'){
//                res.append((char)(s.charAt(i) - 'A' + 'a'));
//            }else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z'){
//                res.append((char)(s.charAt(i) - 'a' + 'A'));
//            }else{
//                res.append(s.charAt(i));
//            }
//        }
//        res = res.reverse();
//        for(int i = 0;i < n;i++){
//            int j = i;
//            while(j < n && res.charAt(j) != ' '){
//                j++;
//            }
//            String temp = res.substring(i,j);
//            StringBuffer buffer = new StringBuffer(temp);
//            temp = buffer.reverse().toString();
//            res.replace(i,j,temp);
//            i = j;
//        }
//        return res.toString();
//    }
//}

// 84 最长公共前缀
//public class Solution {
//    public String longestCommonPrefix (String[] strs) {
//        int n = strs.length;
//        if(n == 0){
//            return "";
//        }
//        for(int i = 0;i < strs[0].length();i++){
//            char temp = strs[0].charAt(i);
//            for(int j = 1;j < n;j++){
//                if(i == strs[j].length() || strs[j].charAt(i) != temp){
//                    return strs[0].substring(0,i);
//                }
//            }
//        }
//        return strs[0];
//    }
//}

// 85 验证IP地址
//public class Solution {
//    public String solve (String IP) {
//        if(isIPv4(IP)){
//            return "IPv4";
//        }else if(isIPv6(IP)){
//            return "IPv6";
//        }
//        return "Neither";
//    }
//
//    boolean isIPv4(String IP){
//        if(IP.indexOf('.') == -1){
//            return false;
//        }
//        String[] s = IP.split("\\.");
//        if(s.length != 4){
//            return false;
//        }
//        for(int i = 0;i < s.length;i++){
//            if(s[i].length() == 0){
//                return false;
//            }
//            if(s[i].length() < 0 || s[i].length() > 3 || s[i].charAt(0) == '0' && s[i].length() != 1){
//                return false;
//            }
//            int num = 0;
//            for(int j = 0;j < s[i].length();j++){
//                char c = s[i].charAt(j);
//                if(c < '0' || c > '9'){
//                    return false;
//                }
//                num = num * 10 + (int)(c - '0');
//                if(num < 0 || num > 255){
//                    return false;
//                }
//            }
//        }
//        return true;
//    }
//
//    boolean isIPv6(String IP){
//        if(IP.indexOf(':') == -1){
//            return false;
//        }
//        String[] s = IP.split(":",-1);
//        if(s.length != 8){
//            return false;
//        }
//        for(int i = 0;i < s.length;i++){
//            if(s[i].length() == 0 || s[i].length() > 4){
//                return false;
//            }
//            for(int j = 0;j < s[i].length();j++){
//                char c = s[i].charAt(j);
//                boolean expr = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f')  || (c >= 'A' && c <= 'F') ;
//                if(!expr){
//                    return false;
//                }
//            }
//        }
//        return true;
//    }
//}

// 86 大数加法
// public class Solution {
//    public String solve (String s, String t) {
//        if(s.length() <= 0){
//            return t;
//        }
//        if(t.length() <= 0){
//            return s;
//        }
//        if(s.length() < t.length()){
//            String temp = s;
//            s = t;
//            t = temp;
//        }
//        int carry = 0;
//        char[] res =  new char[s.length()];
//        for(int i = s.length() - 1;i >= 0;i--){
//            int temp = s.charAt(i) - '0' +  carry;
//            int j = i - s.length() + t.length();
//            if(j >= 0){
//                temp += t.charAt(j) - '0';
//            }
//            carry = temp / 10;
//            temp = temp % 10;
//            res[i] = (char)(temp + '0');
//        }
//        String output = String.valueOf(res);
//        //最后的进位
//        if(carry == 1)
//            output = '1' + output;
//        return output;
//    }
//}

//  双指针

// 87 合并两个有序的数组
//public class Solution {
//    public void merge(int A[], int m, int B[], int n) {
//        int a = m - 1;
//        int b = n - 1;
//        for(int i = m + n - 1;i >= 0;i--){
//            if(b < 0 || a >= 0 && A[a] >= B[b]){
//                A[i] = A[a];
//                a--;
//            }else{
//                A[i] = B[b];
//                b--;
//            }
//        }
//    }
//}

// 88 判断是否为回文字符串
// public class Solution {
//     public boolean judge (String str) {
//         int n = str.length();
//         if(n == 0 || n == 1){
//             return true;
//         }
//         int a = 0;
//         int b = n - 1;
//         while(a < b){
//             if(str.charAt(a) != str.charAt(b)){
//                 return false;
//             }
//             a++;
//             b--;
//         }
//         return true;
//     }
// }

// 89 合并区间
// public class Solution {
//     public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
//         ArrayList<Interval> res = new ArrayList<>();
//         if(intervals.size() == 0){
//             return res;
//         }
//         Collections.sort(intervals,new Comparator<Interval>(){
//             public int compare(Interval o1,Interval o2){
//                 if(o1.start != o2.start){
//                     return o1.start - o2.start;
//                 }else{
//                     return o1.end - o2.end;
//                 }
//             }
//         });
//         res.add(intervals.get(0));
//         int count = 0;
//         for(int i = 1;i < intervals.size();i++){
//             Interval o1 = intervals.get(i);
//             Interval origin = res.get(count);
//             if(o1.start > origin.end){
//                 res.add(o1);
//                 count++;
//             }else{
//                 res.remove(count);
//                 Interval s = new Interval(origin.start,o1.end);
//                 if(o1.end < origin.end){
//                     s.end = origin.end;
//                 }
//                 res.add(s);
//             }
//         }
//         return res;
//     }
// }

// 90 最小覆盖子串
// public class Solution {
//     public String minWindow (String S, String T) {
//         int cnt = S.length() + 1;
//         int[] hash = new int[128];
//         for(int i = 0;i < T.length();i++){
//             hash[T.charAt(i)] -= 1;
//         }
//         int slow = 0,fast = 0;
//         int left = -1,right = -1;
//         for(;fast < S.length();fast++){
//             char c = S.charAt(fast);
//             hash[c]++; 
//             while(check(hash)){
//                 if(cnt > fast - slow + 1){
//                     cnt = fast - slow + 1;
//                     left = slow;
//                     right = fast;
//                 }
//                 c = S.charAt(slow);
//                 hash[c]--;
//                 slow++;
//             }
//         }
//         if(left == -1){
//             return "";
//         }
//         return S.substring(left,right+1);
//     }
//     boolean check(int hash[]){
//         for(int i = 0;i < hash.length;i++){
//             if(hash[i] < 0){
//                 return false;
//             }
//         }
//         return true;
//     }
// }

// 91 反转字符串
// public class Solution {
//     /**
//      * 反转字符串
//      * @param str string字符串 
//      * @return string字符串
//      */
//     public String solve (String str) {
//         if(str == null || str.length() == 0){
//             return str;
//         }
//         StringBuffer s = new StringBuffer(str);
//         return s.reverse().toString();
//     }
// }

// 92 最长无重复子数组
//public class Solution {
//    /**
//     *
//     * @param arr int整型一维数组 the array
//     * @return int整型
//     */
//    public int maxLength (int[] arr) {
//        HashMap<Integer,Integer> map = new HashMap<>();
//        int res = 0;
//        for(int left = 0,right=0;right < arr.length;right++){
//            if(map.containsKey(arr[right])){
//                map.put(arr[right],map.get(arr[right])+1);
//            }else{
//                map.put(arr[right],1);
//            }
//
//            while(map.get(arr[right]) > 1){
//                map.put(arr[left],map.get(arr[left++]) - 1);
//            }
//            res = Math.max(res,right - left + 1);
//        }
//        return res;
//    }
//}

// 93 盛水最多的容器
// public class Solution {
//     public int maxArea (int[] height) {
//         int n = height.length;
//         if(n < 2){
//             return 0;
//         }
//         int res = 0;
//         int left = 0;
//         int right = height.length - 1;
//         while(left < right){
//             int capacity = Math.min(height[left],height[right]) * (right - left);
//             res = Math.max(res,capacity);
//             if(height[left] < height[right]){
//                 left++;
//             }else{
//                 right--;
//             }
//         }
//         return res;
//     }
// }

// 94 接雨水问题
// public class Solution {
//     public long maxWater (int[] arr) {
//         if(arr.length < 3){
//             return 0;
//         }
//         int res = 0;
//         int left = 0;
//         int right = arr.length - 1;
//         int maxL = 0;
//         int maxR = 0;
//         while(left < right){
//             maxL = Math.max(maxL,arr[left]);
//             maxR = Math.max(maxR,arr[right]);
//             if(maxR > maxL){
//                 res += maxL - arr[left++];
//             }else{
//                 res += maxR - arr[right--];
//             }
//         }
//         return res;
//     }
// }


//   贪心算法

// 95 分糖果问题
// public class Solution {
//     public int candy (int[] arr) {
//         int n = arr.length;
//         if(n <= 1){
//             return n;
//         }
//         int[] nums = new int[n];
//         Arrays.fill(nums,1);
//         for(int i = 1;i < arr.length;i++){
//             if(arr[i] > arr[i-1]){
//                 nums[i] = nums[i - 1] + 1;
//             }
//         }
//         int res = nums[n - 1];
//         for(int i = arr.length - 2;i >= 0;i--){
//             if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]){
//                 nums[i] = nums[i+1] + 1;
//             }
//             res += nums[i];
//         }
//         return res;
//     }
// }

// 96 主持人调度（二）
// public class Solution {
//     public int minmumNumberOfHost (int n, int[][] startEnd) {
//         int[] start = new int[n];
//         int[] end = new int[n];
//         for(int i = 0;i < n;i++){
//             start[i] = startEnd[i][0];
//             end[i] = startEnd[i][1];
//         }
//         Arrays.sort(start);
//         Arrays.sort(end);
//         int res = 0;
//         int j = 0;
//         for(int i = 0;i < n;i++){
//             if(start[i] >= end[j]){
//                 j++;
//             }else{
//                 res++;
//             }
//         }
//         return res;
//     }
// }

// 模拟

// 97 旋转数组
// public class Solution {
    // public int[] solve (int n, int m, int[] a) {
    //     m = m % n;
    //     reverse(a,0,n-1);
    //     reverse(a,0,m-1);
    //     reverse(a,m,n-1);
    //     return a;
    // }
    // public void reverse(int[] nums,int start,int end){
    //     while(start < end){
    //         swap(nums,start++,end--);
    //     }
    // }
    // public void swap(int[] nums,int a,int b){
    //     int temp = nums[a];
    //     nums[a] = nums[b];
    //     nums[b] = temp;
    // }
// }

// 98 螺旋矩阵
// public class Solution {
//     public ArrayList<Integer> spiralOrder(int[][] matrix) {
//         ArrayList<Integer> res = new ArrayList<>();
//         if(matrix.length == 0){
//             return res;
//         }
//         int left = 0;
//         int right = matrix[0].length - 1;
//         int up = 0;
//         int down = matrix.length-1;
//         while(left <= right && up <= down){
//             for(int i = left;i <= right;i++){
//                 res.add(matrix[up][i]);
//             }
//             up++;
//             if(up > down){
//                 break;
//             }
//             for(int i = up;i <= down;i++){
//                 res.add(matrix[i][right]);
//             }
//             right--;
//             if(right < left){
//                 break;
//             }
//             for(int i = right;i >= left;i--){
//                 res.add(matrix[down][i]);
//             }
//             down--;
//             if(up > down){
//                 break;
//             }
//             for(int i = down;i >= up;i--){
//                 res.add(matrix[i][left]);
//             }
//             left++;
//             if(left > right){
//                 break;
//             }
//         }
//         return res;
//     }
// }

// 99 顺时针旋转矩阵
// public class Solution {
//     public int[][] rotateMatrix(int[][] mat, int n) {
//         for(int i = 0;i < n;i++){
//             for(int j = 0;j < i;j++){
//                 int temp = mat[i][j];
//                 mat[i][j] = mat[j][i];
//                 mat[j][i] = temp;
//             }
//         }
//         for(int i = 0;i < n;i++){
//             for(int j = 0;j < n/2;j++){
//                 int temp = mat[i][j];
//                 mat[i][j] = mat[i][n-j-1];
//                 mat[i][n - j - 1] = temp;
//             }
//         }
//         return mat;
//     }
// }

// 100 设计 LRU 缓存结构
// public class Solution {
//      static class Node{
//           int key;
//           int value;
//           Node prev;
//           Node next;
//           Node(int key,int value,Node prev,Node next){
//                this.key = key;
//                this.value = value;
//                this.prev  = prev;
//                this.next = next;
//           }
//      }

//      private int capacity;
//      private Map<Integer,Node> map;
//      private Node head;
//      private Node tail;
//      private int used;

//     public Solution(int capacity) {
//          this.capacity = capacity;
//          this.map = new HashMap<>();
//          this.used = 0;
//     }

//     public int get(int key) {
//          if(!map.containsKey(key)){
//               return -1;
//          }
//          makeRecently(key);
//          return map.get(key).value;
//     }

//     public void set(int key, int value) {
//          if(map.containsKey(key)){
//               map.get(key).value = value;
//               makeRecently(key);
//               return;
//          }
//          if(used == capacity){
//               map.remove(tail.key);
//               tail = tail.prev;
//               tail.next = null;
//               used--;
//          }
//          if(head == null){
//               head = new Node(key,value,null,null);
//               tail = head;
//          }else{
//               Node t = new Node(key,value,null,head);
//               head.prev = t;
//               head = t;
//          }
//          map.put(key,head);
//          used++;
//     }
//     // 把 对应的节点移动到链表头部
//     private void makeRecently(int key){
//          Node t = map.get(key);
//          if(t != head){
//               if(t == tail){
//                    tail = tail.prev;
//                    tail.next = null;
//               }else{
//                    t.prev.next = t.next;
//                    t.next.prev = t.prev;
//               }
//               t.prev = null;
//               t.next = head;
//               head.prev = t;
//               head = t;
//          }
//     }
// }

// 101 设计LFU缓存结构
// public class Solution {
//      static class Node{
//          int freq;
//          int key;
//          int val;
//          public Node(int freq,int key,int val){
//              this.freq = freq;
//              this.key = key;
//              this.val = val;
//          }
//      }
//     //  频率到双向链表的哈希表
//      private Map<Integer,LinkedList<Node>> freq_mp = new HashMap<>();
//     // key 到节点的哈希表
//      private Map<Integer,Node> map = new HashMap<>();
//     //  记录缓存的剩余容量
//     private int size = 0;
//     // 记录当前最小频次
//     private int min_freq = 0;

//     public int[] LFU (int[][] operators, int k) {
//         // 构建初始化连接
//         // 链表剩余大小
//         this.size = k;
//         // 原频率中删除该节点
//         int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
//         int[] res = new int[len];
//         // 遍历所有操作
//         for(int i = 0,j = 0;i < operators.length;i++){
//             if(operators[i][0] == 1){
//                 set(operators[i][1],operators[i][2]);
//             }else{
//                 // get 操作
//                 res[j++] = get(operators[i][1]);
//             }
//         }
//         return res;
//     }
//     // 调用函数时，更新频率 或者 val 值
//     private void update(Node node,int key,int value){
//         int freq = node.freq;
//         freq_mp.get(freq).remove(node);
//         if(freq_mp.get(freq).isEmpty()){
//             freq_mp.remove(freq);
//             if(min_freq == freq){
//                 min_freq++;
//             }
//         }
//         if(!freq_mp.containsKey(freq + 1)){
//             freq_mp.put(freq + 1,new LinkedList<Node>());
//         }
//         // 插入频率加一的双向链表表头，链表中对应：freq key value
//         freq_mp.get(freq + 1).addFirst(new Node(freq+1,key,value));
//         map.put(key,freq_mp.get(freq + 1).getFirst());
//     }
//     private void set(int key,int value){
//         // 咋哈希表中找到key值
//         if(map.containsKey(key)){
//             update(map.get(key),key,value);
//         }else{
//             if(size == 0){
//                 // 满容量取频率最低且最早的删掉
//                 int oldkey = freq_mp.get(min_freq).getLast().key;
//                 // 频率哈希表的链表中删除
//                 freq_mp.get(min_freq).removeLast();
//                 if(freq_mp.get(min_freq).isEmpty()){
//                     freq_mp.remove(min_freq);
//                 }
//                 map.remove(oldkey);
//             }else{
//                 size--;
//             }
//             // 最小频率置为 1
//             min_freq = 1;
//             // 在频率为 1 的双向链表表头插入该键
//             if(!freq_mp.containsKey(1)){
//                 freq_mp.put(1,new LinkedList<Node>());
//             }
//             freq_mp.get(1).addFirst(new Node(1,key,value));
//             map.put(key,freq_mp.get(1).getFirst());
//         }
//     }
//     public int get(int key){
//         int res = -1;
//         if(map.containsKey(key)){
//             Node node = map.get(key);
//             res = node.val;
//             update(node,key,res);
//         }
//         return res;
//     }
// }